# 方法一
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        n = len(s)
        ret = set()
        for i in range(n):
            j = n - 1
            while i < j:
                if s[i] != s[j]:
                    j -= 1
                else:
                    for k in range(i + 1, j):
                        item = (s[i], s[k], s[j])
                        if item not in ret:
                            ans += 1
                            ret.add(item)
                    break
        return ans 

# 方法二，优化
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        n = len(s)
        ret = set()
        pre = set() # 记录回文串前后字母
        for i in range(n):
            if s[i] not in pre: # 如果现在字母已出现过直接跳过
                pre.add(s[i])
            else:
                continue
            j = n - 1
            while i < j:
                if s[i] != s[j]:
                    j -= 1
                else:
                    for k in range(i + 1, j):
                        item = (s[i], s[k], s[j])
                        if item not in ret:
                            ans += 1
                            ret.add(item)
                    break
        return ans 
# 灵神代码
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        for alpha in ascii_lowercase:  # 枚举两侧字母 alpha
            i = s.find(alpha)  # 最左边的 alpha 的下标
            if i < 0:  # s 中没有 alpha
                continue
            j = s.rfind(alpha)  # 最右边的 alpha 的下标
            ans += len(set(s[i + 1: j]))  # 统计有多少个不同的中间字母
        return ans